package com.jjlin.leetcode;

import java.util.LinkedList;
import java.util.List;

public class Solution17 {
    String[] letterMap = new String[]{"", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //数字到字母的映射表
    List<String> res = new LinkedList<>(); //队列

    //解法1：使用回溯(DFS)
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0)
            return res;
        backtrack(digits, new StringBuilder(), 0);
        return res;
    }

    //回溯
    public void backtrack(String digits, StringBuilder letter, int index){
        if(index == digits.length()){ //终止条件
            res.add(letter.toString());
            return;
        }
        int letterIndex = digits.charAt(index) - '0';
        String str = letterMap[letterIndex];
        int len = str.length();
        for(int i = 0; i < len; i++){
            letter.append(str.charAt(i));
            backtrack(digits, letter, index + 1);
            letter.deleteCharAt(letter.length() - 1);//记得删除该位置的字符，为同个位置的下个字符回溯做准备
        }
    }

    //解法二：使用队列(BFS)
    public List<String> letterCombinations1(String digits) {
        if(digits == null || digits.length() == 0)
            return res;
        int len = digits.length();
        res.add(""); //先往队列中加入一个空字符
        for(int index = 0; index < len; index++){
            String str = letterMap[digits.charAt(index) - '0']; //获得数字对应的字符串
            int strLen = str.length();
            int size = res.size(); //获得队列的长度
            for(int i = 0; i < size; i++){
                String ch = res.remove(0); //出队
                for(int j = 0; j < strLen; j++)
                    res.add(ch + str.charAt(j)); //入队
            }
        }
        return res;
    }
}
